home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / dynahash.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  23KB  |  1,015 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)dynahash.c  5.14 (Berkeley) 4/2/91";
  39. #endif /* LIBC_SCCS and not lint */
  40. #undef DEBUG
  41. #define KERNEL
  42. #include "ixnet.h"
  43. #include <sys/param.h>
  44. #include <sys/stat.h>
  45. #include <fcntl.h>
  46. #include <errno.h>
  47. #include <db.h>
  48. #include <stdio.h>
  49. #include <stdlib.h>
  50. #include <unistd.h>
  51. #include <string.h>
  52. #include "hash.h"
  53. #include "utils.h"
  54.  
  55. #define assert(x) \
  56. { \
  57.     if(!x) {\
  58.     fprintf(stderr,"assertion failed on line %d, in file %s\n",__LINE__,__FILE__); \
  59.     exit(1);\
  60.     }\
  61. }
  62.  
  63. /* Fast arithmetic, relying on powers of 2, */
  64.  
  65. #define MOD(x,y)                ((x) & ((y)-1))
  66. #undef RETURN_ERROR
  67. #define RETURN_ERROR(ERR,LOC)   { save_errno = ERR; goto LOC; }
  68.  
  69. /* Return values */
  70.  
  71. #define SUCCESS 0
  72. #define ERROR    -1
  73. #define ABNORMAL 1
  74.  
  75.  
  76. /* hash function */
  77. extern int (*default_hash)();
  78.  
  79.  
  80. /* Internal routines */
  81. static HTAB *init_hash();
  82. static int hash_access();
  83. static int flush_meta();
  84. static int alloc_segs();
  85. static int init_htab();
  86. static char *hash_realloc();
  87. static int hdestroy();
  88. static int hash_put();
  89. static int hash_delete();
  90. static int hash_get();
  91. static int hash_sync();
  92. static int hash_close();
  93. static int hash_seq();
  94. #if 0
  95. static void swap_header_copy();
  96. static void swap_header();
  97. #endif
  98. /* Local data */
  99.  
  100. HTAB *hashp = NULL;
  101.  
  102. #ifdef HASH_STATISTICS
  103. long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
  104. #endif
  105.  
  106. /************************** INTERFACE ROUTINES **********************/
  107. /* OPEN/CLOSE */
  108.  
  109. extern    DB *
  110. hash_open ( file, flags, mode, info )
  111. const char    *file;
  112. int    flags;
  113. int    mode;
  114. const HASHINFO    *info;        /* Special directives for create */
  115. {
  116.     int     bpages;
  117.     int     hdrsize;
  118.     int     new_table = 0;
  119.     int     nsegs;
  120.     int     save_errno;
  121.     struct    stat statbuf;
  122.     DB        *dbp;
  123.  
  124.  
  125.     if ( !(hashp = (HTAB *) calloc( 1, sizeof(HTAB) ))) {
  126.     /* calloc should set errno */
  127.     return(0);
  128.     }
  129.     hashp->fp = -1;
  130.     /*
  131.     Select flags relevant to us.
  132.     Even if user wants write only, we need to be able to read
  133.     the actual file, so we need to open it read/write.  But, the
  134.     field in the hashp structure needs to be accurate so that
  135.     we can check accesses.
  136.     */
  137.     flags = flags & (O_CREAT | O_EXCL | O_RDONLY | O_RDWR | O_TRUNC | O_WRONLY);
  138.     hashp->flags = flags;
  139.     if ( flags & O_WRONLY )  flags = (flags & ~O_WRONLY) | O_RDWR;
  140.  
  141.     if ( !file ||
  142.      (flags & O_TRUNC) ||
  143.      (stat ( file, &statbuf ) && (errno == ENOENT)) ) {
  144.      if ( errno == ENOENT ) {
  145.         errno = 0;        /* Just in case someone looks at errno */
  146.      }
  147.      new_table = 1;
  148.     }
  149.  
  150.     if ( file ) {
  151.     if ((hashp->fp = open ( file, flags, mode )) == -1) {
  152.         RETURN_ERROR (errno, error0);
  153.     }
  154.     (void)fcntl(hashp->fp, F_SETFD, 1);
  155.     }
  156.  
  157.     if ( new_table ) {
  158.     if ( !(hashp = init_hash( info )) ) {
  159.         RETURN_ERROR(errno,error1);
  160.     }
  161.     } else {
  162.     /* Table already exists */
  163.     if ( info && info->hash ) hashp->hash = info->hash;
  164.     else hashp->hash = default_hash;
  165.  
  166.     hdrsize = read ( hashp->fp, &hashp->hdr, sizeof(HASHHDR) );
  167. #if BYTE_ORDER == LITTLE_ENDIAN
  168.     swap_header ( );
  169. #endif
  170.     if ( hdrsize == -1 ) {
  171.         RETURN_ERROR(errno, error1);
  172.     }
  173.     if ( hdrsize != sizeof(HASHHDR) ) {
  174.         RETURN_ERROR(EFTYPE, error1);
  175.     }
  176.  
  177.     /* Verify file type, versions and hash function */
  178.     if ( hashp->MAGIC != HASHMAGIC )
  179.         RETURN_ERROR ( EFTYPE, error1 );
  180.     if ( hashp->VERSION != VERSION_NO )
  181.         RETURN_ERROR ( EFTYPE, error1 );
  182.     if (hashp->hash ( CHARKEY, sizeof(CHARKEY) ) != hashp->H_CHARKEY ) {
  183.         RETURN_ERROR ( EFTYPE, error1 );
  184.     }
  185.  
  186.     /*
  187.         Figure out how many segments we need.
  188.     */
  189.     nsegs = (hashp->MAX_BUCKET + hashp->SGSIZE -1)/ hashp->SGSIZE;
  190.     hashp->nsegs = 0;
  191.     if (alloc_segs( nsegs )) {
  192.         /*
  193.         If alloc_segs fails, table will have been destroyed
  194.         and errno will have been set.
  195.         */
  196.         return( (DB *) NULL );
  197.     }
  198.  
  199.     /* Read in bitmaps */
  200.     bpages = (hashp->SPARES[__log2(hashp->MAX_BUCKET)] +
  201.           (hashp->BSIZE << BYTE_SHIFT) - 1) >>
  202.           (hashp->BSHIFT + BYTE_SHIFT);
  203.  
  204.     hashp->nmaps = bpages;
  205.     memset ( &hashp->mapp[0], 0, bpages * sizeof ( u_long *) );
  206.     }
  207.  
  208.     /* Initialize Buffer Manager */
  209.     if ( info && info->cachesize ) {
  210.     __buf_init (info->cachesize);
  211.     } else {
  212.     __buf_init (DEF_BUFSIZE);
  213.     }
  214.  
  215.     hashp->new_file = new_table;
  216.     hashp->save_file = file && (hashp->flags & (O_WRONLY|O_RDWR));
  217.     hashp->cbucket = -1;
  218.     if ( !(dbp = (DB *)malloc ( sizeof (DB) )) ) {
  219.     save_errno = errno;
  220.     hdestroy();
  221.     errno = save_errno;
  222.     return ( NULL );
  223.     }
  224.     dbp->internal = (char *)hashp;
  225.     dbp->close = hash_close;
  226.     dbp->del = hash_delete;
  227.     dbp->get = hash_get;
  228.     dbp->put = hash_put;
  229.     dbp->seq = hash_seq;
  230.     dbp->sync = hash_sync;
  231.     dbp->type = DB_HASH;
  232.  
  233. #ifdef DEBUG
  234.     (void)fprintf(stderr, "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
  235.         "init_htab:",
  236.         "TABLE POINTER   ", hashp,
  237.         "BUCKET SIZE     ", hashp->BSIZE,
  238.         "BUCKET SHIFT    ", hashp->BSHIFT,
  239.         "DIRECTORY SIZE  ", hashp->DSIZE,
  240.         "SEGMENT SIZE    ", hashp->SGSIZE,
  241.         "SEGMENT SHIFT   ", hashp->SSHIFT,
  242.         "FILL FACTOR     ", hashp->FFACTOR,
  243.         "MAX BUCKET      ", hashp->MAX_BUCKET,
  244.         "HIGH MASK       ", hashp->HIGH_MASK,
  245.         "LOW  MASK       ", hashp->LOW_MASK,
  246.         "NSEGS           ", hashp->nsegs,
  247.         "NKEYS           ", hashp->NKEYS );
  248. #endif
  249. #ifdef HASH_STATISTICS
  250.     hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
  251. #endif
  252.     return (dbp);
  253.  
  254.     (void)hdestroy();
  255.     errno = save_errno;
  256.     return ( (DB *)NULL );
  257.  
  258. error1:
  259.     (void) close ( hashp->fp );
  260.  
  261. error0:
  262.     free ( hashp );
  263.     errno = save_errno;
  264.     return ( (DB *) NULL );
  265. }
  266.  
  267. static int
  268. hash_close (dbp)
  269. DB    *dbp;
  270. {
  271.     int    retval;
  272.  
  273.     if ( !dbp ) {
  274.         return(ERROR);
  275.     }
  276.     hashp = (HTAB *)dbp->internal;
  277.     retval = hdestroy();
  278.     (void)free ( dbp );
  279.     return ( retval );
  280. }
  281.  
  282.  
  283. /************************** LOCAL CREATION ROUTINES **********************/
  284. static HTAB *
  285. init_hash( info )
  286. HASHINFO *info;
  287. {
  288.     int    nelem;
  289.  
  290.     nelem = 1;
  291.  
  292.     hashp->LORDER    = BYTE_ORDER;
  293.     hashp->BSIZE    = DEF_BUCKET_SIZE;
  294.     hashp->BSHIFT    = DEF_BUCKET_SHIFT;
  295.     hashp->SGSIZE    = DEF_SEGSIZE;
  296.     hashp->SSHIFT    = DEF_SEGSIZE_SHIFT;
  297.     hashp->DSIZE    = DEF_DIRSIZE;
  298.     hashp->FFACTOR    = DEF_FFACTOR;
  299.     hashp->hash    = default_hash;
  300.     bzero (hashp->SPARES, sizeof (hashp->SPARES));
  301.  
  302.     if ( info ) {
  303.         if ( info->bsize )   {
  304.         /* Round pagesize up to power of 2 */
  305.         hashp->BSHIFT  = __log2(info->bsize);
  306.         hashp->BSIZE   = 1 << hashp->BSHIFT;
  307.         if ( hashp->BSIZE > MAX_BSIZE ) {
  308.             errno = EINVAL;
  309.             return(0);
  310.         }
  311.         }
  312.         if ( info->ffactor )  hashp->FFACTOR = info->ffactor;
  313.         if ( info->hash ) hashp->hash    = info->hash;
  314.         if ( info->nelem ) nelem = info->nelem;
  315.         if ( info->lorder ) {
  316.         if ( info->lorder != BIG_ENDIAN &&
  317.              info->lorder != LITTLE_ENDIAN) {
  318.             errno = EINVAL;
  319.             return(0);
  320.         }
  321.         hashp->LORDER = info->lorder;
  322.         }
  323.     }
  324.  
  325.     /* init_htab should destroy the table and set errno if it fails */
  326.     if ( init_htab ( nelem ) ) {
  327.         return(0);
  328.     } else {
  329.         return(hashp);
  330.     }
  331. }
  332.  
  333. /*
  334.     This calls alloc_segs which may run out of memory.
  335.     Alloc_segs will destroy the table and set errno,
  336.     so we just pass the error information along.
  337.  
  338.     Returns 0 on No Error
  339.  
  340. */
  341. static int
  342. init_htab ( nelem )
  343. int    nelem;
  344. {
  345.     register int nbuckets;
  346.     register int nsegs;
  347.     int    l2;
  348.  
  349.  /*
  350.   * Divide number of elements by the fill factor and determine a desired
  351.   * number of buckets.    Allocate space for the next greater power of
  352.   * two number of buckets
  353.   */
  354.     nelem = (nelem - 1) / hashp->FFACTOR + 1;
  355.  
  356.     l2 = __log2(nelem);
  357.     nbuckets = 1 << l2;
  358.     nbuckets = MAX ( nbuckets, 2 );
  359.  
  360.     hashp->SPARES[l2] = l2 + 1;
  361.     hashp->SPARES[l2+1] = l2 + 1;
  362.     /*
  363.         First bitmap page is at:
  364.         splitpoint l2
  365.         page offset 1
  366.     */
  367.     __init_bitmap ( OADDR_OF(l2,1), l2+1, 0 );
  368.  
  369.     hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
  370.     hashp->HIGH_MASK = (nbuckets << 1) - 1;
  371.     hashp->HDRPAGES = ((MAX(sizeof(HASHHDR),MINHDRSIZE) - 1) >>
  372.               hashp->BSHIFT) + 1;
  373.  
  374.     nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
  375.     nsegs = 1 << __log2(nsegs);
  376.  
  377.     if ( nsegs > hashp->DSIZE ) {
  378.         hashp->DSIZE  = nsegs;
  379.     }
  380.  
  381.     return (alloc_segs ( nsegs ) );
  382. }
  383.  
  384. /********************** DESTROY/CLOSE ROUTINES ************************/
  385.  
  386. /*
  387.     Flushes any changes to the file if necessary and
  388.     destroys the hashp structure, freeing all allocated
  389.     space.
  390. */
  391. static int
  392. hdestroy()
  393. {
  394.     int    save_errno;
  395.     int    i;
  396.  
  397.     save_errno = 0;
  398.  
  399.     if (hashp != NULL) {
  400. #ifdef HASH_STATISTICS
  401.      (void) fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
  402.             hash_accesses, hash_collisions);
  403.      (void) fprintf(stderr, "hdestroy: expansions %ld\n",
  404.             hash_expansions);
  405.      (void) fprintf(stderr, "hdestroy: overflows %ld\n",
  406.             hash_overflows);
  407.      (void) fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
  408.             hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
  409.  
  410.     for ( i = 0; i < NCACHED; i++ ) {
  411.         (void) fprintf ( stderr, "spares[%d] = %d\n", i, hashp->SPARES[i] );
  412.     }
  413. #endif
  414.  
  415.         /*
  416.             Call on buffer manager to free buffers, and if
  417.             required, write them to disk
  418.         */
  419.         if (__buf_free(1, hashp->save_file)) {
  420.             save_errno = errno;
  421.         }
  422.         if ( hashp->dir ) {
  423.             (void)free(*hashp->dir);    /* Free initial segments */
  424.             /* Free extra segments */
  425.             while ( hashp->exsegs-- ) {
  426.             (void)free ( hashp->dir[--hashp->nsegs] );
  427.             }
  428.             (void)free(hashp->dir);
  429.         }
  430.         if (flush_meta() && !save_errno) {
  431.             save_errno = errno;
  432.         }
  433.  
  434.         /* Free Bigmaps */
  435.         for ( i = 0; i < hashp->nmaps; i++ ) {
  436.             if ( hashp->mapp[i] ) {
  437.             (void) free ( hashp->mapp[i] );
  438.             }
  439.         }
  440.  
  441.         if ( hashp->fp != -1 ) {
  442.             (void)close (hashp->fp);
  443.         }
  444.         (void)free(hashp);
  445.         hashp = NULL;
  446.     }
  447.     if ( save_errno ) {
  448.         errno = save_errno;
  449.         return(ERROR);
  450.     } else {
  451.         return(SUCCESS);
  452.     }
  453. }
  454.  
  455. /*
  456.     Write modified pages to disk
  457.     0 == OK
  458.     -1 ERROR
  459. */
  460. static int
  461. hash_sync(dbp)
  462. DB    *dbp;
  463. {
  464.     if ( !dbp ) {
  465.         return (ERROR);
  466.     }
  467.  
  468.     hashp = (HTAB *)dbp->internal;
  469.  
  470.     if (!hashp->save_file) return(0);
  471.     if ( __buf_free ( 0, 1 )  || flush_meta()) {
  472.         return(ERROR);
  473.     }
  474.     hashp->new_file = 0;
  475.     return(0);
  476. }
  477.  
  478. /*
  479. 0 == OK
  480. -1 indicates that errno should be set
  481. */
  482. static int
  483. flush_meta()
  484. {
  485.     int    fp;
  486.     int    i;
  487.     int    wsize;
  488.     HASHHDR *whdrp;
  489.  
  490.     if (!hashp->save_file) return(0);
  491.     hashp->MAGIC = HASHMAGIC;
  492.     hashp->VERSION = VERSION_NO;
  493.     hashp->H_CHARKEY = hashp->hash ( CHARKEY, sizeof(CHARKEY));
  494.  
  495.     fp = hashp->fp;
  496.     whdrp = &hashp->hdr;
  497. #if BYTE_ORDER == LITTLE_ENDIAN
  498.     whdrp = &whdr;
  499.     swap_header_copy( &hashp->hdr, whdrp );
  500. #endif
  501.     if ( (lseek (fp, 0, SEEK_SET) == -1 ) ||
  502.          ((wsize = write ( fp, whdrp, sizeof(HASHHDR))) == -1)) {
  503.         return(-1);
  504.     } else if ( wsize != sizeof(HASHHDR) ) {
  505.         errno = EFTYPE;
  506.         hashp->tab_errno = errno;
  507.         return(-1);
  508.     }
  509.     for ( i = 0; i < NCACHED; i++ ) {
  510.         if ( hashp->mapp[i] ) {
  511.         if (!__put_page((char *)hashp->mapp[i],
  512.             hashp->BITMAPS[i], 0, 1)){
  513.             return(-1);
  514.         }
  515.         }
  516.     }
  517.     return(0);
  518. }
  519. /*******************************SEARCH ROUTINES *****************************/
  520. /*
  521.     All the access routines return
  522.     0 on SUCCESS
  523.     1 to indicate an external ERROR (i.e. key not found, etc)
  524.     -1 to indicate an internal ERROR (i.e. out of memory, etc)
  525. */
  526. static int
  527. hash_get ( dbp, key, data, flag )
  528. DB    *dbp;
  529. DBT    *key, *data;
  530. u_int    flag;
  531. {
  532. #ifdef lint
  533.     flag = flag;
  534. #endif
  535.  
  536.     if ( !dbp ) {
  537.     return (ERROR);
  538.     }
  539.     hashp = (HTAB *)dbp->internal;
  540.     if ( hashp->flags & O_WRONLY ) {
  541.     errno = EBADF;
  542.     hashp->tab_errno = errno;
  543.     return ( ERROR );
  544.     }
  545.     return ( hash_access ( HASH_GET, key, data ) );
  546. }
  547.  
  548. static int
  549. hash_put ( dbp, key, data, flag )
  550. DB    *dbp;
  551. DBT    *key, *data;
  552. u_int    flag;
  553. {
  554.     if ( !dbp ) {
  555.     return (ERROR);
  556.     }
  557.     hashp = (HTAB *)dbp->internal;
  558.     if ( (hashp->flags & O_ACCMODE) == O_RDONLY ) {
  559.     errno = EBADF;
  560.     hashp->tab_errno = errno;
  561.     return ( ERROR );
  562.     }
  563.     if ( flag == R_NOOVERWRITE ) {
  564.     return ( hash_access ( HASH_PUTNEW, key, data ) );
  565.     } else {
  566.     return ( hash_access ( HASH_PUT, key, data ) );
  567.     }
  568. }
  569.  
  570. static int
  571. hash_delete ( dbp, key, flag )
  572. DB    *dbp;
  573. DBT    *key;
  574. u_int    flag;        /* Ignored */
  575. {
  576. #ifdef lint
  577.     flag = flag;
  578. #endif
  579.     if ( !dbp ) {
  580.     return (ERROR);
  581.     }
  582.     hashp = (HTAB *)dbp->internal;
  583.     if ( (hashp->flags & O_ACCMODE) == O_RDONLY ) {
  584.     errno = EBADF;
  585.     hashp->tab_errno = errno;
  586.     return ( ERROR );
  587.     }
  588.     return ( hash_access ( HASH_DELETE, key, NULL ) );
  589. }
  590.  
  591. /*
  592.     Assume that hashp has been set in wrapper routine
  593. */
  594. static int
  595. hash_access(action, key, val)
  596. HASH_ACTION action;
  597. DBT *key, *val;
  598. {
  599.     register    BUFHEAD *rbufp;
  600.     register    u_short *bp;
  601.     register    int    ndx;
  602.     register    int n;
  603.     register    int off = hashp->BSIZE;
  604.     register    int        size;
  605.     register    char    *kp;
  606.     BUFHEAD *bufp;
  607.     BUFHEAD *save_bufp;
  608.     u_short pageno;
  609.  
  610. #ifdef HASH_STATISTICS
  611.     hash_accesses++;
  612. #endif
  613.  
  614.     size = key->size;
  615.     kp = (char *)key->data;
  616.     rbufp = __get_buf ( __call_hash(kp, size), NULL, 0 );
  617.     if ( !rbufp ) return(ERROR);
  618.     save_bufp = rbufp;
  619.  
  620.     /* Pin the bucket chain */
  621.     rbufp->flags |= BUF_PIN;
  622.     for ( bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;  ) {
  623.         if ( bp[1] >= REAL_KEY ) {
  624.         /* Real key/data pair */
  625.         if (size == off - *bp &&
  626.             bcmp(kp, rbufp->page + *bp, size) == 0) {
  627.             goto found;
  628.         }
  629.         off = bp[1];
  630. #ifdef HASH_STATISTICS
  631.         hash_collisions++;
  632. #endif
  633.         bp += 2;
  634.         ndx += 2;
  635.         } else if ( bp[1] == OVFLPAGE ) {
  636.         rbufp = __get_buf ( *bp, rbufp, 0 );
  637.         if ( !rbufp ) {
  638.             save_bufp->flags &= ~BUF_PIN;
  639.             return (ERROR);
  640.         }
  641.         /* FOR LOOP INIT */
  642.         bp = (u_short *)rbufp->page;
  643.         n = *bp++;
  644.         ndx = 1;
  645.         off = hashp->BSIZE;
  646.         } else if ( bp[1] < REAL_KEY ) {
  647.         if ( (ndx = __find_bigpair(rbufp, ndx, kp, size )) > 0 ) {
  648.             goto found;
  649.         } else if ( ndx == -2 ) {
  650.             bufp = rbufp;
  651.             if ( !(pageno = __find_last_page ( &bufp )) ) {
  652.             ndx = 0;
  653.             rbufp = bufp;
  654.             break;    /* FOR */
  655.             }
  656.             rbufp = __get_buf ( pageno, bufp, 0 );
  657.             if ( !rbufp ) {
  658.             save_bufp->flags &= ~BUF_PIN;
  659.             return (ERROR);
  660.             }
  661.             /* FOR LOOP INIT */
  662.             bp = (u_short *)rbufp->page;
  663.             n = *bp++;
  664.             ndx = 1;
  665.             off = hashp->BSIZE;
  666.         } else    {
  667.             save_bufp->flags &= ~BUF_PIN;
  668.             return(ERROR);
  669.         }
  670.         }
  671.     }
  672.  
  673.     /* Not found */
  674.     switch ( action ) {
  675.         case HASH_PUT:
  676.         case HASH_PUTNEW:
  677.         if (__addel(rbufp, key, val)) {
  678.             save_bufp->flags &= ~BUF_PIN;
  679.             return(ERROR);
  680.         } else {
  681.             save_bufp->flags &= ~BUF_PIN;
  682.             return(SUCCESS);
  683.         }
  684.         case HASH_GET:
  685.         case HASH_DELETE:
  686.         default:
  687.         save_bufp->flags &= ~BUF_PIN;
  688.         return(ABNORMAL);
  689.     }
  690.  
  691. found:
  692.     switch (action) {
  693.         case HASH_PUTNEW:
  694.         save_bufp->flags &= ~BUF_PIN;
  695.         return(ABNORMAL);
  696.         case HASH_GET:
  697.         bp = (u_short *)rbufp->page;
  698.         if (bp[ndx+1] < REAL_KEY) __big_return(rbufp, ndx, val, 0);
  699.         else {
  700.             val->data = (u_char *)rbufp->page + (int) bp[ndx + 1];
  701.             val->size = bp[ndx] - bp[ndx + 1];
  702.         }
  703.         break;
  704.         case HASH_PUT:
  705.         if ((__delpair (rbufp, ndx)) || (__addel (rbufp, key, val)) ) {
  706.             save_bufp->flags &= ~BUF_PIN;
  707.             return(ERROR);
  708.         }
  709.         break;
  710.         case HASH_DELETE:
  711.         if (__delpair (rbufp, ndx))return(ERROR);
  712.         break;
  713.         default:
  714.         break;
  715.     }
  716.     save_bufp->flags &= ~BUF_PIN;
  717.     return (SUCCESS);
  718. }
  719.  
  720. static int
  721. hash_seq(dbp, key, data, flag)
  722. DB    *dbp;
  723. DBT    *key, *data;
  724. u_int    flag;
  725. {
  726.     register    u_int bucket;
  727.     register    BUFHEAD *bufp;
  728.     u_short *bp = NULL;
  729.     u_short ndx;
  730.  
  731.     if ( !dbp ) {
  732.         return (ERROR);
  733.     }
  734.  
  735.     hashp = (HTAB *)dbp->internal;
  736.     if ( hashp->flags & O_WRONLY ) {
  737.         errno = EBADF;
  738.         hashp->tab_errno = errno;
  739.         return ( ERROR );
  740.     }
  741. #ifdef HASH_STATISTICS
  742.     hash_accesses++;
  743. #endif
  744.  
  745.     if ( (hashp->cbucket < 0) || (flag == R_FIRST) ) {
  746.         hashp->cbucket = 0;
  747.         hashp->cndx = 1;
  748.         hashp->cpage = NULL;
  749.     }
  750.  
  751.     if ( !(bufp = hashp->cpage) ) {
  752.         for (bucket = hashp->cbucket;
  753.          bucket <= hashp->MAX_BUCKET;
  754.          bucket++, hashp->cndx = 1 ) {
  755.  
  756.         bufp = __get_buf ( bucket, NULL, 0 );
  757.         if (!bufp) return(ERROR);
  758.         hashp->cpage = bufp;
  759.         bp = (u_short *)bufp->page;
  760.         if (bp[0]) break;
  761.         }
  762.         hashp->cbucket = bucket;
  763.         if ( hashp->cbucket > hashp->MAX_BUCKET ) {
  764.         hashp->cbucket = -1;
  765.         return ( ABNORMAL );
  766.         }
  767.     } else {
  768.         bp    = (u_short *)hashp->cpage->page;
  769.     }
  770.  
  771. #ifdef DEBUG
  772.     assert (bp);
  773.     assert (bufp);
  774. #endif
  775.     while ( bp[hashp->cndx+1] == OVFLPAGE ) {
  776.         bufp = hashp->cpage = __get_buf ( bp[hashp->cndx], bufp, 0 );
  777.         if (!bufp) return(ERROR);
  778.         bp = (u_short *)(bufp->page);
  779.         hashp->cndx = 1;
  780.     }
  781.     ndx = hashp->cndx;
  782.     if (bp[ndx+1] < REAL_KEY) {
  783.         if (__big_keydata(bufp, ndx, key, data, 1)) {
  784.         return(ERROR);
  785.         }
  786.     } else {
  787.         key->data = (u_char *)hashp->cpage->page + bp[ndx];
  788.         key->size = (ndx > 1 ? bp[ndx-1] : hashp->BSIZE) - bp[ndx];
  789.         data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];
  790.         data->size = bp[ndx] - bp[ndx + 1];
  791.         ndx += 2;
  792.         if ( ndx > bp[0] ) {
  793.         hashp->cpage = NULL;
  794.         hashp->cbucket++;
  795.         hashp->cndx=1;
  796.         } else hashp->cndx = ndx;
  797.     }
  798.     return (SUCCESS);
  799. }
  800.  
  801. /********************************* UTILITIES ************************/
  802. /*
  803.     0 ==> OK
  804.     -1 ==> Error
  805. */
  806. extern int
  807. __expand_table()
  808. {
  809.     u_int    old_bucket, new_bucket;
  810.     int    new_segnum;
  811.     int    dirsize;
  812.     int    spare_ndx;
  813. #ifdef HASH_STATISTICS
  814.     hash_expansions++;
  815. #endif
  816.  
  817.     new_bucket = ++hashp->MAX_BUCKET;
  818.     old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
  819.  
  820.     new_segnum = new_bucket >> hashp->SSHIFT;
  821.  
  822.     /* Check if we need a new segment */
  823.     if ( new_segnum >= hashp->nsegs ) {
  824.  
  825.         /* Check if we need to expand directory */
  826.         if ( new_segnum >= hashp->DSIZE ) {
  827.  
  828.         /* Reallocate directory */
  829.         dirsize = hashp->DSIZE * sizeof ( SEGMENT * );
  830.         if (!hash_realloc ( &hashp->dir, dirsize, (dirsize << 1 ) )) {
  831.             return(-1);
  832.         }
  833.         hashp->DSIZE = dirsize << 1;
  834.         }
  835.         if (!(hashp->dir[new_segnum] =
  836.             (SEGMENT)calloc ( hashp->SGSIZE, sizeof(SEGMENT)))) {
  837.             return(-1);
  838.         }
  839.         hashp->exsegs++;
  840.         hashp->nsegs++;
  841.     }
  842.  
  843.     /*
  844.         If the split point is increasing (MAX_BUCKET's log
  845.         base 2 increases), we need to copy the current contents
  846.         of the spare split bucket to the next bucket
  847.     */
  848.     spare_ndx = __log2(hashp->MAX_BUCKET);
  849.     if ( spare_ndx != (__log2(hashp->MAX_BUCKET - 1))) {
  850.         hashp->SPARES[spare_ndx] = hashp->SPARES[spare_ndx-1];
  851.     }
  852.  
  853.     if ( new_bucket > hashp->HIGH_MASK ) {
  854.         /* Starting a new doubling */
  855.         hashp->LOW_MASK = hashp->HIGH_MASK;
  856.         hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
  857.     }
  858.  
  859.     /*
  860.      * Relocate records to the new bucket
  861.      */
  862.     return(__split_page ( old_bucket, new_bucket ));
  863. }
  864. /*
  865.     If realloc guarantees that the pointer is not destroyed
  866.     if the realloc fails, then this routine can go away
  867. */
  868. static char *
  869. hash_realloc ( p_ptr, oldsize, newsize )
  870. char    **p_ptr;
  871. int    oldsize;
  872. int    newsize;
  873. {
  874.     register char    *p;
  875.  
  876.        p = (char *)malloc ( newsize );
  877.        if ( p ) {
  878.         bcopy ( *p_ptr, p, oldsize );
  879.         bzero ( *p_ptr + oldsize, newsize-oldsize );
  880.         free(*p_ptr);
  881.         *p_ptr = p;
  882.     }
  883.     return (p);
  884. }
  885.  
  886. extern u_int
  887. __call_hash ( k, len )
  888. char    *k;
  889. int    len;
  890. {
  891.     int    n, bucket;
  892.     n = hashp->hash(k, len);
  893.  
  894.     bucket = n & hashp->HIGH_MASK;
  895.     if ( bucket > hashp->MAX_BUCKET ) {
  896.         bucket = bucket & hashp->LOW_MASK;
  897.     }
  898.  
  899.     return(bucket);
  900. }
  901.  
  902. /*
  903.     Allocate segment table.  On error, destroy the table
  904.     and set errno.
  905.  
  906.     Returns 0 on success
  907. */
  908. static int
  909. alloc_segs ( nsegs )
  910. int    nsegs;
  911. {
  912.     register int    i;
  913.     register SEGMENT    store;
  914.  
  915.     int save_errno;
  916.  
  917.     if (!(hashp->dir = (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *)))) {
  918.     save_errno = errno;
  919.     (void)hdestroy();
  920.     errno = save_errno;
  921.     return(-1);
  922.     }
  923.  
  924.     /* Allocate segments */
  925.     store = (SEGMENT)calloc ( nsegs << hashp->SSHIFT, sizeof (SEGMENT) );
  926.     if ( !store ) {
  927.     save_errno = errno;
  928.     (void)hdestroy();
  929.     errno = save_errno;
  930.     return(-1);
  931.     }
  932.  
  933.     for ( i=0; i < nsegs; i++, hashp->nsegs++ ) {
  934.     hashp->dir[i] = &store[i<<hashp->SSHIFT];
  935.     }
  936.     return(0);
  937. }
  938.  
  939. #if 0 /* not used */
  940. /*
  941.     Hashp->hdr needs to be byteswapped.
  942. */
  943. static void
  944. swap_header_copy ( srcp, destp )
  945. HASHHDR *srcp;
  946. HASHHDR *destp;
  947. {
  948.     int i;
  949.  
  950.     BLSWAP_COPY(srcp->magic, destp->magic);
  951.     BLSWAP_COPY(srcp->version, destp->version);
  952.     BLSWAP_COPY(srcp->lorder, destp->lorder);
  953.     BLSWAP_COPY(srcp->bsize, destp->bsize);
  954.     BLSWAP_COPY(srcp->bshift, destp->bshift);
  955.     BLSWAP_COPY(srcp->dsize, destp->dsize);
  956.     BLSWAP_COPY(srcp->ssize, destp->ssize);
  957.     BLSWAP_COPY(srcp->sshift, destp->sshift);
  958.     BLSWAP_COPY(srcp->max_bucket, destp->max_bucket);
  959.     BLSWAP_COPY(srcp->high_mask, destp->high_mask);
  960.     BLSWAP_COPY(srcp->low_mask, destp->low_mask);
  961.     BLSWAP_COPY(srcp->ffactor, destp->ffactor);
  962.     BLSWAP_COPY(srcp->nkeys, destp->nkeys);
  963.     BLSWAP_COPY(srcp->hdrpages, destp->hdrpages);
  964.     BLSWAP_COPY(srcp->h_charkey, destp->h_charkey);
  965.     for ( i=0; i < NCACHED; i++ ) {
  966.     BLSWAP_COPY ( srcp->spares[i] , destp->spares[i]);
  967.     BSSWAP_COPY ( srcp->bitmaps[i] , destp->bitmaps[i]);
  968.     }
  969.     return;
  970. }
  971.  
  972. static void
  973. swap_header ( )
  974. {
  975.     HASHHDR    *hdrp;
  976.     int i;
  977.  
  978.     hdrp = &hashp->hdr;
  979.  
  980.     BLSWAP(hdrp->magic);
  981.     BLSWAP(hdrp->version);
  982.     BLSWAP(hdrp->lorder);
  983.     BLSWAP(hdrp->bsize);
  984.     BLSWAP(hdrp->bshift);
  985.     BLSWAP(hdrp->dsize);
  986.     BLSWAP(hdrp->ssize);
  987.     BLSWAP(hdrp->sshift);
  988.     BLSWAP(hdrp->max_bucket);
  989.     BLSWAP(hdrp->high_mask);
  990.     BLSWAP(hdrp->low_mask);
  991.     BLSWAP(hdrp->ffactor);
  992.     BLSWAP(hdrp->nkeys);
  993.     BLSWAP(hdrp->hdrpages);
  994.     BLSWAP(hdrp->h_charkey);
  995.     for ( i=0; i < NCACHED; i++ ) {
  996.     BLSWAP ( hdrp->spares[i] );
  997.     BSSWAP ( hdrp->bitmaps[i] );
  998.     }
  999.     return;
  1000. }
  1001. #endif
  1002.  
  1003.  
  1004. int
  1005. __log2( num )
  1006. int    num;
  1007. {
  1008.     register int    i;
  1009.     register int    limit = 1;
  1010.  
  1011.     for ( i = 0; limit < num; limit = limit << 1, i++ );
  1012.     return (i);
  1013. }
  1014.  
  1015.